package com.shm.leetcode;

import java.util.Arrays;

/**
 * 1752. 检查数组是否经排序和轮转得到
 * 给你一个数组 nums 。nums 的源数组中，所有元素与 nums 相同，但按非递减顺序排列。
 *
 * 如果 nums 能够由源数组轮转若干位置（包括 0 个位置）得到，则返回 true ；否则，返回 false 。
 *
 * 源数组中可能存在 重复项 。
 *
 * 注意：我们称数组 A 在轮转 x 个位置后得到长度相同的数组 B ，当它们满足 A[i] == B[(i+x) % A.length] ，其中 % 为取余运算。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [3,4,5,1,2]
 * 输出：true
 * 解释：[1,2,3,4,5] 为有序的源数组。
 * 可以轮转 x = 3 个位置，使新数组从值为 3 的元素开始：[3,4,5,1,2] 。
 * 示例 2：
 *
 * 输入：nums = [2,1,3,4]
 * 输出：false
 * 解释：源数组无法经轮转得到 nums 。
 * 示例 3：
 *
 * 输入：nums = [1,2,3]
 * 输出：true
 * 解释：[1,2,3] 为有序的源数组。
 * 可以轮转 x = 0 个位置（即不轮转）得到 nums 。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 100
 * 1 <= nums[i] <= 100
 */
public class Check {
    public boolean check(int[] nums) {
        int size = nums.length;
        int[] sortNums = new int[size];
        System.arraycopy(nums, 0, sortNums, 0, size);
        Arrays.sort(sortNums);
        int[] changeNums = new int[size];
        for(int x=0;x<size;x++) {
            int i=0;
            for(;i<size;i++){
                changeNums[i] = sortNums[(i+x)%size];
                if (changeNums[i]!=nums[i]){
                    break;
                }
            }
            if(i==size) {
                return true;
            }
        }
        return false;
    }

    /**
     * 方法一：直接遍历
     * 思路与算法
     *
     * 按照题意可以知道 \textit{nums}nums 的源数组 \textit{source}source 中的所有元素都按非递减顺序排列，假设数组的长度为 nn，假设当数组向右轮转 xx 个位置，令 x = x \mod nx=xmodn，根据置换公式 \textit{source}[i] = \textit{nums}[(i + x) \mod n]source[i]=nums[(i+x)modn] 可以知道：
     *
     * \textit{nums}[0,\cdots,x-1] = \textit{source}[n-x,\cdots,n-1] \\ \textit{nums}[x,\cdots,n-1] = \textit{source}[0,\cdots,n-x-1] \\
     * nums[0,⋯,x−1]=source[n−x,⋯,n−1]
     * nums[x,⋯,n−1]=source[0,⋯,n−x−1]
     *
     * 当 x = 0x=0 时，则意味着数组 \textit{nums}nums 本身为非递减顺序排列，\textit{nums}nums 与原数组相同，此时我们只需要判断 \textit{nums}nums 是否为非递减顺序排列；
     *
     * 当 x > 0x>0 时，则意味着数组 \textit{nums}nums 分为了两部分，\textit{nums}[0,\cdots,x-1],\textit{nums}[x,\cdots,n-1]nums[0,⋯,x−1],nums[x,⋯,n−1]，需进行分类检测；
     *
     * 对于 x > 0x>0 时，根据题意可以知道对于原始数组 \textit{source}source 一定满足当 i \le ji≤j 时，则 \textit{source}[i] \le \textit{source}[j]source[i]≤source[j]，由此我们可以推出：
     *
     * 当 0 < i < x0<i<x 时，则一定满足 \textit{nums}[i-1] \le \textit{nums}[i]nums[i−1]≤nums[i]；
     * 当 x < i < nx<i<n 时，则一定满足 \textit{nums}[i-1] \le \textit{nums}[i]nums[i−1]≤nums[i]；
     * 当 x \le i < nx≤i<n 时，由于 \textit{source}[n-x-1] \le \textit{source}[n-x]source[n−x−1]≤source[n−x]，则一定满足 \textit{nums}[i] \le \textit{nums}[n-1] \le \textit{nums}[0]nums[i]≤nums[n−1]≤nums[0]；
     * 当满足 \textit{source}[n-1] = \textit{source}[0]source[n−1]=source[0] 时，则意味着整个数组均为相等，从任意处轮转数组均保持不变；
     * 当满足 \textit{source}[n-1] > \textit{source}[0]source[n−1]>source[0] 时，此时 \textit{source}[n-1],\textit{source}[0]source[n−1],source[0] 对应的元素为 \textit{nums}[x-1],\textit{nums}[x]nums[x−1],nums[x]，此时一定满足 \textit{nums}[x-1] > \textit{nums}[x]nums[x−1]>nums[x]，则此时找到第一个索引 ii 满足 \textit{nums}[i] < \textit{nums}[i - 1]nums[i]<nums[i−1] 时，\textit{nums}[i-1],\textit{nums}[i]nums[i−1],nums[i] 对应着源数组中的 \textit{source}[n-1],\textit{source}[0]source[n−1],source[0]；
     * 根据上述推理，我们检测过程如下：
     *
     * 首先检测数组是否非递减排序，如果满足非递减排序则直接返回 \text{true}true；
     * 如果数组不满足非递减排序，则找到第一个 ii 满足 \textit{nums}[i] < \textit{nums}[i - 1]nums[i]<nums[i−1]，然后分别检测子数组 \textit{nums}[0,\cdots,i-1],\textit{nums}[i,\cdots,n-1]nums[0,⋯,i−1],nums[i,⋯,n−1] 是否都满足非递减排序；
     * 如果两个子数组都满足非递减排序，还需检测 \textit{nums}[i,\cdots,n-1]nums[i,⋯,n−1] 中的元素是否都满足小于等于 \textit{nums}[0]nums[0]，实际我们只需检测 \textit{nums}[n-1]nums[n−1] 是否满足小于等于 \textit{nums}[0]nums[0] 即可；
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode.cn/problems/check-if-array-is-sorted-and-rotated/solution/jian-cha-shu-zu-shi-fou-jing-pai-xu-he-l-cbqk/
     * @return
     */
    public boolean check_1(int[] nums) {
        int size = nums.length;

        for(int x=1;x<size;x++) {
            //首先检测数组是否非递减排序，如果满足非递减排序则直接返回
            if(nums[x]>=nums[x-1]) {
            }else {
                int i=x+1;
                for(;i<size;i++) {
                    if(nums[i]<nums[i-1]) {
                        return false;
                    }
                }
                if (i==size) {
                    return nums[size-1] <= nums[0];
                }
            }
        }
        return true;
    }

    public boolean check_2(int[] nums) {
        int n = nums.length, x = 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] < nums[i - 1]) {
                x = i;
                break;
            }
        }
        if (x == 0) {
            return true;
        }
        for (int i = x + 1; i < n; ++i) {
            if (nums[i] < nums[i - 1]) {
                return false;
            }
        }
        return nums[0] >= nums[n - 1];
    }

}
